#include "LinkTree.h"
#include <iostream>

/* 构造函数 = 构建节点 */
Node::Node(ElementType element)
{
    data = element;
    parent = nextSibling =firstChild = nullptr;//初始化指针
}

/* 将当前节点连接到双亲上 */
void Node::Connect(Node *parent)
{
    if(parent == nullptr)
        return;

    this->parent = parent;
    //用头插法插入，o(1)
    //无序树，使用头插，先插入的在后面
    this->nextSibling = parent->firstChild;
    parent->firstChild = this;
}

/* 移除节点：只是跟双亲及兄弟断开*/
void Node::DisConnect()
{
    if(parent == nullptr)   //树为空，则直接返回
        return;
    /* 如果我是第一个孩子 */
    if(this == parent->firstChild)  //如果删除的为第一个子树
    {
        parent->firstChild = this->nextSibling;     //直接进行删除操作
    }
    /* 如果我不是第一个孩子 */
    else    //如果删除的不是第一个子树，需进行遍历找到之后再删除
    {
        Node * travelPoint = parent->firstChild;    //创建遍历指针travelPoint
        while(travelPoint->nextSibling != nullptr)  //遍历到空指针为止
        {
            if(travelPoint->nextSibling == this)    //找到子树进行删除——单链表删除操作
            {
                travelPoint->nextSibling = this->nextSibling;
                break;  //跳出循环
            }
            travelPoint = travelPoint->nextSibling;
        }
    }
    //个人理解为类似删除链表的释放空间
    this->nextSibling = nullptr;  //断开之后无兄弟树，兄弟树为空
    this->parent = nullptr;       //断开之后无双亲，双亲为空
}

/* 打印树 */
void Node::TravelNode(Node *node, int depth,void(*showPtr)(ElementType))
{
    //终止条件
    if(node == nullptr)
        return;
        
    for(int i = 0; i < depth; i++)
    {
        printf("  ");
        // std::cout<<"  ";
    }
    if(depth != 0)
    {
        printf("%s","|_");
        // std::cout<<" |_";
    }
    //std::cout<<node->data<<std::endl;   //不为空则输出自己数据
    showPtr(node->data);//showPtr代替了std：：cout
    TravelNode(node->firstChild,depth + 1,showPtr);
    TravelNode(node->nextSibling,depth,showPtr);

    /* 广度优先遍历 */
    // TravelNode(node->nextSibling);      //广度优先遍历，先找兄弟
    // TravelNode(node->firstChild);       //调换一下位置就是深度优先
}

/*…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………*/

/* 获取父节点 */
Node *Node::GetParent() const
{
    return parent;
}
/* 获取data */
ElementType Node::GetData()
{
    return data;
}


/*………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………*/


LinkTree::LinkTree()
{
    root = new Node(0); //构造一个新的节点，初始化值为0，空节点
}

LinkTree::~LinkTree()
{
    FreeNode(root);//调用释放的递归
}

/* 获取根节点 */
Node *LinkTree::GetRoot() const
{
    return root;//只需要获得private中的root
}

/* 打印树 */
void LinkTree::show()
{
    //打印树的时候要传showPtr指针
    Node::TravelNode(root->firstChild,0,showPtr);//firstChild在树中的private，需友元调用
}

/* 释放节点 */
void LinkTree::FreeNode(Node *node)
{
    //终止条件
    if(node == nullptr)     //如果节点为空直接返回
        return;
    
    /* 等同两次递归 */
    // Node * travelPoint = node->firstChild;  //创建遍历节点
    // while(travelPoint != nullptr)   
    // {
    //     Node * nextNode = travelPoint->nextSibling; //记下下一个节点
    //     FreeNode(travelPoint);   //放当前节点的孩子
    //     travelPoint = nextNode;  //继续放下一个节点
    // }

    /* 翻过来写就是先释放兄弟再释放孩子*/
    FreeNode(node->firstChild);     //先释放孩子直到没有孩子
    FreeNode(node->nextSibling);    //再释放兄弟直到没有孩子

    // std::cout<<node->data<<std::endl;
    delete node;                    //最后释放我自己
}

/* 获取树的高度 */
int LinkTree::GetNodeHeight(Node *node)
{
    //终止条件
    if(node == nullptr)
        return 0;

    int MaxChildHeight = 0;
    Node * travelPoint = node->firstChild;//计算node下一层的高度
    while(travelPoint != nullptr)
    {
        int childHeight = GetNodeHeight(travelPoint);   //计算下一层孩子的高度
        MaxChildHeight = MaxChildHeight > childHeight ? MaxChildHeight : childHeight;   //取最大高度
        travelPoint = travelPoint->nextSibling;         //计算兄弟的层次，接下去遍历
    }
    return MaxChildHeight + 1;//加1加的是node这一层
}
/* 调用获取树的高度的函数 */
int LinkTree::GetTreeHeight()
{
    return GetNodeHeight(root) - 1; //根节点不放值,是虚假节点
}

/* 查找节点 */
Node *LinkTree::FindNode(Node *node, ElementType element)
{
    if(node == nullptr)
        return nullptr;

    if(IsEqualPtr(node->data,element))
        return node;
    
    Node * targetNode = FindNode(node->nextSibling,element);
    if(targetNode)  //如果targetNode不为空
        return targetNode;

    targetNode = FindNode(node->firstChild,element);
    if(targetNode)
        return targetNode;

    return nullptr;
}
/* 调用查找节点 */
Node *LinkTree::FindNode(ElementType element)
{
    return FindNode(root->firstChild,element);  //从root的第一个孩子开始找
}

/* ………………回调函数……………… */
/* 展示show的类型 *///！
void LinkTree::SetShowtype(void (*showPtr)(ElementType))
{
    this->showPtr = showPtr;
}
/* */
void LinkTree::SetFindType(bool (*IsEqual)(ElementType,ElementType))
{
    //通过将IsEqual函数的指针赋值给IsEqualPtr成员变量，可以实现通过指针调用函数的功能。
    this->IsEqualPtr = IsEqual;
}









// //创建节点，初始化
// LinkTree::Node *LinkTree::CreateNode(ElementType element)
// {
//     Node * newNode = new Node;
//     newNode->data = element;
//     //双亲、子树、兄弟都为空
//     newNode->parent = newNode->firstChild = newNode->nextSibling = nullptr;

//     return newNode;
// }


